💻 Kth Best-Selling Product using Heap Sort

Learn to find the Kth best-selling product efficiently with heap operations.

📋 Problem Statement

🛒 Story:

Amit, an e-commerce manager, wants to track the top-selling products. He needs the Kth best-selling product from sales data.

📌 Input:

  • First line: n (number of products)
  • Second line: n space-separated integers (sales data)
  • Third line: K (rank to retrieve)

📌 Output:

Print the Kth best-selling product based on sales data.

Constraints:

  • 1 ≤ n ≤ 105
  • 1 ≤ sales ≤ 109
  • 1 ≤ K ≤ n

Sample Input/Output

Input:
5
10 20 15 5 25
2
Output:
20

🔄 Heap-Based Strategy

Steps to Find Kth Largest:

  1. Build a max-heap from the sales data
  2. Repeat K-1 times: Swap root with last element, reduce heap size, heapify
  3. Root now holds the Kth largest element

Time Complexity

O(n + K log n)

Space Complexity

O(1) in-place

🔍 Step-by-Step Heap Demo

Heap State

Press Start to begin heap operations

🎮 Interactive Practice

Your result will appear here.

Sample Test Cases (click to fill inputs)

Input: 5 10 20 15 5 25 | K=2 → Output: 20
Input: 50 30 40 20 10 25 15 35 | K=4 → Output: 30
Input: 5 3 1 6 4 2 | K=3 → Output: 4

📊 Analysis & Takeaways

Heap Sort Highlights:

  1. Max-heap ensures root is always the largest element
  2. Extracting K-1 times gives Kth largest at the root
  3. In-place heap reduces extra space usage

Time Complexity

O(n + K log n)

Space Complexity

O(1)